%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definición del tipo de documento.                                           %
% Posibles tipos de papel: a4paper, letterpaper, legalpapper                  %
% Posibles tamaños de letra: 10pt, 11pt, 12pt                                 %
% Posibles clases de documentos: article, report, book, slides                %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[a4paper,11pt]{article}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Los paquetes permiten ampliar las capacidades de LaTeX.                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Paquete para inclusión de gráficos.
\usepackage{graphicx}

% Paquete para definir la codificación del conjunto de caracteres usado
% (latin1 es ISO 8859-1).
\usepackage[utf8]{inputenc}

% Paquete para definir el idioma usado.
%\usepackage[spanish]{babel}
\usepackage{float}

\usepackage{listings}
\usepackage[outdir=./]{epstopdf}

% Título principal del documento.
\title{		\textbf{Trabajo práctico 1: \\ Conjunto de instrucciones MIPS \\[3ex]}}

% Información sobre los autores.
\author	{ 	Daddario Rubén, \textit{Padrón Nro. 83122}                      \\
            \texttt{ ruben.daddario@gmail.com }                             \\[3ex]            
            Amura Federico, \textit{Padrón Nro. 95202}							\\
			\texttt{federicoamura@gmail.com}           					    \\[3ex]
            \normalsize{Grupo Nro. X - 2do. Cuatrimestre de 2014}                       \\
            \normalsize{66.20 Organización de Computadoras}                           \\
            \normalsize{Facultad de Ingeniería, Universidad de Buenos Aires}          \\
       }

\date{Jueves 27 de septiembre de 2014}

\begin{document}

% Inserta el título.
\maketitle

% Quita el número en la primera página.
\thispagestyle{empty}

% Resumen
\begin{abstract}
El presente informe se corresponde al trabajo práctico número 1 de la asignatura 66.20 Organización de Computadoras. El trabajo consiste en la implementacion de un programa que por consola verifica la integridad de los tags anidados en un archivo xml. Es decir, el programa verifica que todo tag abierto, tenga luego su correspondiente cerrado y que entre ellos esten bien anidados.
La finalidad del trabajo es en realidad, realizar una parte de la programacion en Assembly para MIPS32.
\end{abstract}

\newpage

\tableofcontents

\newpage

\section{Introducción}

MIPS (Microprocessor without Interlocked Pipeline Stages) es un procesador con arquitectura RISC (reduced instruction set computer) desarrollado por MIPS Technologies. Este tipo de procesadores se encuentra en muchos sistemas embebidos y dispositivos de la actualidad como consolas de videojuegos, routers, etc. En particular, debido a que los diseñadores crearon un conjunto de instrucciones tan claro, los cursos sobre arquitectura de computadoras en unviersidades y escuelas técnicas a menudo se basan en la arquitectura MIPS.

Existen múltiples versiones de este procesador, siendo los más recientes MIPS32 y MIPS64, implementadas para 32 y 64 bits, respectivamente.

\section{Desarrollo}

El programa a elaborar es una implementación en ANSI C y Assembly para MIPS32 de un XML validator. Resumiendo, su funcion es la de validar la correcta utilizacion de los tags en un archivo XML, es decir, ver que todo tag sea abierto y cerrado y que esten correctamente anidados entre si.

\section{Diseño y detalles de implementación}

\subsection{Recursos utilizados}

Para resolver el problema planteado utilizamos la herramienta GXemul para emular un entorno MIPS y el sistema operativo NetBSD. También utilizamos code::blocks para la codificación de la aplicación en C y un repositorio SVN para compartir el proyecto. Para la codificacion en Assembly, se usaron procesadores de texto como el Gedit. Finalmente el programa fue compilado utilizando GCC. 

Para implementar el programa utilizamos el lenguaje de programación C, en su totalidad para la version portable, y las partes especificas para MIPS32 fueron escritas en el Assembly correspondiente siguiendo el ABI de la catedra. Para la realización del informe utilizamos \LaTeX{}.

\subsection{Diseño}

El programa se compone de múltiples archivos de cabecera .h con sus correspondientes archivos .c donde se realiza la implementación de los métodos utilizados.

\begin{center}
\texttt{tp1 [OPTION]...[FILE]...}
\end{center}

Las opciones pueden ser:
\begin{itemize}
\item -h, --help 		Prints usage information
\item -V, --version 		Prints version information
\item -i, --input		Path to input file (-i - for stdin)
\end{itemize}


\subsection{Implementación}

\subsubsection{Portabilidad}

Para proveer portabilidad se implementaron las funciones en lenguaje C para dar soporte genérico a aquellos entornos que carezcan de una versión más específica. Siempre cumpliendo con el estandar ANSI C.

\subsubsection{Código y algoritmos}
El programa se compone de un archivo main con el punto de entrada al ejecutable y desde aquí se invócan al resto de los archivos que definen las estructuras de datos necesarias para la ejecución.
Sin ampliar demasiado ya que el foco del trabajo es la codificacion en Assembly, el programa se dividio en 5 partes.
\begin{itemize}
\item Main, encargado de la entrada del programa e invocar las demas partes
\item Options Reader, cuya tarea es recibir el vector de parametros para la ejecucion del programa y procesarlo para que su utilizacion en el programa sea mas facil.
\item Program Options, que sirve para imprimir la ayuda y liberar las opciones de ejecucion alojadas en memoria dinamica
\item File reader, es la parte encargada de cargar el archivo en memoria (se supone que la memoria puede alojarlo)
\item Validator, que incluye todas las funciones que se utilizaran para la validacion del archivo. Esta seccion fue luego dividida entre sus funciones para facilitar el paso a Assembly.
\end{itemize}

\subsubsection{Desarrollo en Assembly}

Primero se desarrollo la version en C ya que la version general es escrita totalmente en este lenguaje y la version especifica para MIPS32 contiene la mayoria del codigo tambien en el mismo. Como solo se tenia que desarrollar la funcion Validate y las que este utilice en Assembly, se tomaron ciertas medidas extra en su desarrollo. La mas notoria es que no esta toda contenida en un solo archivo .c si no que se encuentra en varios, cada uno incluyendo una sola funcion. Esta division tiene como finalidad facilitar el paso de esas funciones al codigo ensamblador, es una variante de la estrategia de division y conquista. Gracias a esto podemos ir pasando de a una funcion por vez, como tambien trabajarlas aisladamente e incluso probarlas cuando una ya esta lista, sin tener que esperar al resto. 

La codificacion en Assembly se hizo teniendo en cuenta el ABI de la catedra. 

\section{Ejecuciones de prueba}

En esta seccion se muestran algunos ejemplos de ejecucion del programa

\begin{center}
comando utilizado: ./validate sample.xml
\end{center}

\begin{figure}[hbtp]
\caption{Salida de una ejecucion de prueba en NetBSD sobre MIPS32}\label{fig001}
\includegraphics[width=1\textwidth]{ejecucionEnMIPS.eps}
\end{figure}

\begin{figure}[hbtp]
\caption{Salida de una ejecucion de prueba en Ubuntu x86 64bits}\label{fig002}
\includegraphics[width=1\textwidth]{ejecucionEnUbuntu.eps}
\end{figure}

A continuación se muestra la ejecución con un archivo inválido
\begin{center}
comando utilizado: ./validate invalid1.xml
\end{center}

\begin{figure}[hbtp]
\caption{Salida de una ejecucion de un archivo mal armado en Linux}\label{fig003}
\includegraphics[width=1\textwidth]{ejecucionInvalida.eps}
\end{figure}

\begin{figure}[hbtp]
\caption{Archivo valido con codigo de retorno 0}\label{fig004}
\includegraphics[width=1\textwidth]{file1.png}
\end{figure}

\begin{figure}[hbtp]
\caption{Archivo invalido con codigo de retorno 1 utlizando stdin}\label{fig005}
\includegraphics[width=1\textwidth]{file2.png}
\end{figure}

\section{Stacks}

A modo de ayuda graficamos y mostramos un esquema de los stacks armados en las funciones assembly

\begin{figure}[hbtp]
\centering
\caption{Stack funcion validate.S}\label{fig006}
\includegraphics[width=0.7\textwidth]{validateStack.eps}
\end{figure}

\begin{figure}[hbtp]
\centering
\caption{Stack funcion isOpenTag.S}\label{fig007}
\includegraphics[width=0.7\textwidth]{isOpenTagStack.eps}
\end{figure}

\begin{figure}[hbtp]
\centering
\caption{Stack funcion findTag.S}\label{fig008}
\includegraphics[width=0.7\textwidth]{findTagStack.eps}
\end{figure}

\begin{figure}[hbtp]
\centering
\caption{Stack funcion getTagName.S}\label{fig009}
\includegraphics[width=0.7\textwidth]{getTagNameStack.eps}
\end{figure}

\begin{figure}[hbtp]
\centering
\caption{Stack funcion findTagInner.S}\label{fig010}
\includegraphics[width=0.7\textwidth]{findTagInnerStack.eps}
\end{figure}

\newpage

\section{Compilacion}
La compilacion de la version generica, siendo totalmente en C, no varia de un programa comun, se hace simplemente con un archivo Makefile, que envia las ordenes de compilacion para cada archivo y luego la de vinculacion para generar el ejecutable.

En el caso de la version con codigo Assembly, el proceso varia en dos cuestiones. Primero, los archivos que se codificaron en el lenguaje propio del microprocesador con extension .S (mayuscula), deben precompilarse con gcc junto con los .c. Los archivos con extension .S (mayuscula) son interpretados por gcc como archivos a precompilar, a diferencia de los archivos con extension .s (minuscula) que son interpretados como codigo assembly ya pasado por el preprocesador. Un ejemplo de compilacion es el siguiente:

\begin{lstlisting}[language=bash]
gcc -Wall -c *.c *.S
\end{lstlisting}

Luego debemos linkear los archivos para generar el archivo ejecutable:

\begin{lstlisting}[language=bash]
gcc -o validate *.c *.S
\end{lstlisting}

Mas alla de estas dos consideraciones, si todo se ejecuto correctamente entonces el proceso sigue siendo el mismo, terminando con un ejecutable que se comporta de manera similar pero con diferencias internas dado su diferente codificacion.

\section{Conclusiones}

A partir de este trabajo adquirimos experiencia en la compilacion en Assembly y su incorporacion a codigo de un nivel superior.

Tuvimos ademas que lidiar con los warnings generados por el compilador en Assembly y realizar depuracion al mas bajo nivel posible antes de pasar a codigo en binario, viendo como se comportan las instrucciones en un lenguaje como C cuando se las traduce a codigo assembly y luego a codigo maquina.

Tambien vimos como manejar la informacion con la que trabaja el procesador, viendo las instrucciones basicas que este puede realizar y los bloques de datos con los que este opera.

\newpage

% Citas bibliográficas.
\begin{thebibliography}{99}

\bibitem{HEN00} J. L. Hennessy and D. A. Patterson, Computer Architecture. A Quantitative
Approach, 3ra Edicion, Morgan Kaufmann Publishers, 2000.
\bibitem{HEN01} Grupo de la materia http://groups.yahoo.com/group/orga6620/
\bibitem{HEN02} Wikipedia en.wikipedia.org
\bibitem{CBLOCKS} Code::Blocks IDE: www.codeblocks.org

\end{thebibliography}

\end{document}